home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
pctchnqs
/
1992
/
number1
/
l6.c
< prev
next >
Wrap
Text File
|
1992-01-24
|
3KB
|
74 lines
/*
Suite of functions for maintaining a linked list sorted by
ascending order of the Value field. The list is circular; that is,
it has a dummy node as both the head and the tail of the list.
The dummy node is a sentinel, containing the largest possible
Value field setting. Tested with Borland C++ 3.0 in C mode. */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "llist.h"
/* Initializes an empty linked list of LinkNode structures,
consisting of a single head/tail/sentinel node, and returns a
pointer to the list. Returns NULL for failure. */
struct LinkNode *InitLinkedList()
{
struct LinkNode *Sentinel;
if ((Sentinel = malloc(sizeof(struct LinkNode))) == NULL)
return(NULL);
Sentinel->NextNode = Sentinel;
Sentinel->Value = SENTINEL;
strcpy(Sentinel->Text, "*** sentinel ***");
return(Sentinel);
}
/* Finds the first node in a value-sorted linked list with a value
field equal to a key value, and returns a pointer to the node
preceding that node (to facilitate insertion and deletion), or a
NULL pointer if no such value was found. Assumes the list is
terminated with a sentinel node containing the largest possible
value. */
struct LinkNode *FindNodeBeforeValue(struct LinkNode *HeadOfListNode,
int SearchValue)
{
struct LinkNode *NodePtr = HeadOfListNode;
while (NodePtr->NextNode->Value < SearchValue)
NodePtr = NodePtr->NextNode;
if (NodePtr->NextNode->Value == SearchValue) {
/* Found the search value; success unless we found the
sentinel (can happen only if SearchValue == SENTINEL) */
if (NodePtr->NextNode == HeadOfListNode) {
return(NULL); /* failure; we found the sentinel */
} else {
return(NodePtr); /* success; return pointer to node
preceding the node that was equal */
}
} else {
/* No match; return failure status */
return(NULL);
}
}
/* Inserts the specified node into a value-sorted linked list, such
that value-sorting is maintained. Returns a pointer to the node
after which the new node is inserted. */
struct LinkNode *InsertNodeSorted(struct LinkNode *HeadOfListNode,
struct LinkNode *NodeToInsert)
{
struct LinkNode *NodePtr = HeadOfListNode;
int SearchValue = NodeToInsert->Value;
while (NodePtr->NextNode->Value < SearchValue)
NodePtr = NodePtr->NextNode;
NodeToInsert->NextNode = NodePtr->NextNode;
NodePtr->NextNode = NodeToInsert;
return(NodePtr);
}